/*--------------------------------------------------------------------------------
* Copyright (c) 2022,西北农林科技大学信息学院计算机科学系
* All rights reserved.
*
* 文件名称：main.c
* 文件标识：见配置管理计划书
* 摘要：颠倒句子中单词，利用单词栈实现。
*       用sscanf提取原句子中的各个单词，将其压入单词栈。
*       再出栈每个单词拼接结果，根据栈的先入后出特性，得到的是逆序后的单词。
*
* 当前版本：1.0
* 作者：耿楠
* 完成日期：2022年11月26日
*
* 取代版本：无
* 原作者：耿楠
* 完成日期：
------------------------------------------------------------------------------------*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* 栈结点(单词)结构体 */
typedef struct _word
{
    char *wd;           /* 单词字符串指针 */
    size_t len;         /* 单词长度 */
    struct _word *next; /* 指向下一个单词的指针 */
}word;

/* 栈结构体 */
typedef struct _stack_type
{
    word *top;
    size_t word_cnts;
    size_t total_len;
}*word_stack;

/* 栈操作 */
word_stack createStack(const char*);
void destroyStack(word_stack);
void makeEmpty(word_stack);
int isEmpty(word_stack);
int isFull(word_stack);
void pushWord(word_stack, const char *);
char *popWord(word_stack);

/* 判断是否为一个句子 */
int isSentence(const char *, const char *, const char *);
/* 颠倒句子中的单词 */
char* revSentenceWords(char *, const char *, const char *, const char *);

/* 错误响应 */
static void errormsg(const char *);

int main()
{
    /* 句子 */
    /* char s[] = "you can cage a swallow can't you?"; */
    char s[] = "   you can \n  cage a \tswallow  \ncan't you?   ";

    /* 原句子单词分隔符 */
    char delim[] = " \t\n\r";
    /* 句子终止符 */
    char term[] = ".?!";
    /* 结果句子单词分隔符 */
    char hyphen[] = " ";
    char *str = NULL;

    if(isSentence(s, delim, term))
    {
        str = revSentenceWords(s, delim, term, hyphen);
        if(str != NULL)
        {
            puts(str);
            /* free(str); */
        }
    }

    return 0;
}

/* 错误响应 */
static void errormsg(const char *message)
{
    printf("%s\n", message);
    exit(EXIT_FAILURE);
}

/*------------------------------------------------------------------------
// 名称：int isSentence(const char *s, const char *delim, const char *term)
// 功能：判断句子是否有句子终止字符。
// 算法：找到句子尾部不是分隔符(空白)的字符，判断其是不是句子终止字符。
// 参数：
//       [char* s] -------------- 待逆序的字符串的指针
//       [const char* delim] ---- 单词单词分隔字符集指针
//       [const char* term] ----- 句子终止字符集指针
// 返回：[int] --- 有则返回1, 无则返回0
// 作者：耿楠
// 日期：2022年11月26日
------------------------------------------------------------------------*/
int isSentence(const char *s, const char *delim, const char *term)
{
    size_t len = 0;

    len = strlen(s);

    /* 删除尾部分隔符(空白) */
    len = strlen(s) - 1;
    while(strchr(delim, s[len]) && len >= 0)
    {
        len--;
    }

    /* 判断最后有没有句子终止字符 */
    if(!strchr(term, s[len]))
    {
        return 0;
    }

    return 1;
}

/*------------------------------------------------------------------------
// 名称：char* revSentenceWords(char *s, const char *delim,
//                              const char *term, const char *hyphen)
// 功能：将句子按单词逆序(单词必须以空格分隔)。
// 算法：首先构建一个记录单词的栈，然后采用弹出单词，在原字符串空间拼接结果。
// 参数：
//       [char* s] -------------- 待逆序的字符串的指针
//       [const char* delim] ---- 单词单词分隔字符集指针
//       [const char* term] ----- 句子终止字符集指针
//       [const char* hyphen] --- 结果单词分隔字符集指针
// 返回：[char*] --- 逆序后字符串的指针
// 作者：耿楠
// 日期：2022年11月26日
// 注意：处理过程会对原字符串进行改写，如需要保留原串，请在调用该函数前备份。
------------------------------------------------------------------------*/
char* revSentenceWords(char *s, const char *delim,
                       const char *term, const char *hyphen)
{
    char *word, *p;
    char terminator = 0;
    size_t str_len = strlen(s);
    /* 单词栈 */
    word_stack st = NULL;

    /* 记录句子终止字符并删除原句子终止字符 */
    p = s + str_len - 1;
    while(!strchr(term, *p))
    {
        p--;
    }
    terminator = *p;
    *p = '\0';

    /* 构建单词栈(单词存于栈中) */
    st = createStack(s);
    str_len = st->total_len + st->word_cnts;

    /* 清空原串 */
    *s = '\0';

    /* 弹出栈中的字符串，并拼接结果字符串 */
    while(!isEmpty(st))
    {
        word = popWord(st);
        strcat(s, word);
        /* 释放字符串空间 */
        free(word);

        strcat(s, hyphen);
    }

    /* 添加句子终止字符 */
    s[str_len - 1] = terminator;

    /* 删除栈 */
    destroyStack(st);

    return s;
}

/*------------------------------------------------------------------------
// 名称：word_stack createStack(const char *s)
// 功能：创建单词栈。
// 算法：使用sscanf在字符串中循环读入单词后，压入栈中
// 参数：
//       [char* s] --- 待逆序的字符串的指针
// 返回：[word_stack] --- 栈指针
// 作者：耿楠
// 日期：2022年11月26日
------------------------------------------------------------------------*/
word_stack createStack(const char *s)
{
    char *str;
    int off;

    /* 为栈结构申请内存 */
    word_stack st = (word_stack)malloc(sizeof(struct _stack_type));
    if(st == NULL)
    {
        errormsg("Error in create: stack could not be created.");
    }

    /* 申请一个原串长度的字符串，以保存读入的串 */
    str = (char *)malloc((strlen(s) + 1) * sizeof(char));
    if(str == NULL)
    {
        free(st);
        errormsg("Error in create: not enough memory for temp string.");
    }

    /* 初始化栈成员 */
    st->top = NULL;
    st->word_cnts = 0;
    st->total_len = 0;

    /* 使用sscanf从原串中读入各单词 */
    /* %n用于获取每次sscanf读入的字符数以实现字符串的偏移 */
    while(sscanf(s, "%s%n", str, &off) == 1)
    {
        /* 将单词压入栈中 */
        pushWord(st, str);
        s += off;
    }

    /* 释放空间 */
    free(str);

    return st;
}

/*------------------------------------------------------------------------
// 名称：void destroyStack(word_stack st)
// 功能：销毁栈。
// 算法：先清空栈，再释放栈空间
// 参数：
//       [word_stack st] --- 栈指针
// 返回：[void] --- 无
// 作者：耿楠
// 日期：2022年11月26日
------------------------------------------------------------------------*/
void destroyStack(word_stack st)
{
    makeEmpty(st);
    free(st);
}

/*------------------------------------------------------------------------
// 名称：void makeEmpty(word_stack st)
// 功能：清空栈。
// 算法：逐个弹出单词，再释放单词占用的空间
// 参数：
//       [word_stack st] --- 栈指针
// 返回：[void] --- 无
// 作者：耿楠
// 日期：2022年11月26日
------------------------------------------------------------------------*/
void makeEmpty(word_stack st)
{
    char *str;

    while(!isEmpty(st))
    {
        str = popWord(st);
        free(str);
    }
}

/*------------------------------------------------------------------------
// 名称：int isEmpty(word_stack st)
// 功能：判断栈是否为空。
// 参数：
//       [word_stack st] --- 栈指针
// 返回：[int] --- 栈不为空返回1, 为空返回0
// 作者：耿楠
// 日期：2022年11月26日
------------------------------------------------------------------------*/
int isEmpty(word_stack st)
{
    return st->top == NULL;
}

/*------------------------------------------------------------------------
// 名称：int isFULL(word_stack st)
// 功能：判断栈是否为满。
// 参数：
//       [word_stack st] --- 栈指针
// 返回：[int] --- 永远返回0，因为用链表实现，不会出现满栈现象
// 作者：耿楠
// 日期：2022年11月26日
------------------------------------------------------------------------*/
int isFULL(word_stack st)
{
    return 0;
}

/*------------------------------------------------------------------------
// 名称：void pushWord(word_stack st, const char *str)
// 功能：将单词入栈。
// 参数：
//       [word_stack st] ----- 栈指针
//       [const char *str] --- 单词指针
// 返回：[void] --- 无
// 作者：耿楠
// 日期：2022年11月26日
------------------------------------------------------------------------*/
void pushWord(word_stack st, const char *str)
{
    size_t len = strlen(str);
    word *pnew_word = NULL;

    /* 创建新单词 */
    pnew_word = (word*)malloc(sizeof(word));
    if(pnew_word == NULL)
    {
        return;
    }

    /* 创建单词字符串空间 */
    pnew_word->wd = (char*)malloc((len + 1) * sizeof(char));
    if(pnew_word->wd == NULL)
    {
        free(pnew_word);
        return;
    }

    /* 单词结构体成员赋值 */
    strcpy(pnew_word->wd, str);
    pnew_word->len = len;
    /* 单词结构体指针成员指向栈顶 */
    pnew_word->next = st->top;

    /* 调整栈顶指针 */
    st->top = pnew_word;
    /* 单词数 */
    st->word_cnts++;
    /* 单词数累计长度 */
    st->total_len += len;
}

/*------------------------------------------------------------------------
// 名称：char *popWord(word_stack st)
// 功能：将单词出栈。
// 参数：
//       [word_stack st] ----- 栈指针
// 返回：[char *] --- 单词指针
// 作者：耿楠
// 日期：2022年11月26日
------------------------------------------------------------------------*/
char *popWord(word_stack st)
{
    word *p_top;

    char *s;

    /* 栈为空，结束程序 */
    if(isEmpty(st))
    {
        errormsg("Error in pop word: word stack is empty.");
    }

    /* 记录栈顶指针 */
    p_top = st->top;

    /* 记录单词指针 */
    s = p_top->wd;

    /* 调整栈顶指针 */
    st->top = p_top->next;
    /* 减少一个单词 */
    st->word_cnts--;
    /* 减少一个单词的长度 */
    st->total_len -= strlen(s);

    /* 删除栈顶结点 */
    free(p_top);

    return s;
}

